package LinkedList_03.Single_Linked_List_03;

/*
 * @Author 罗
 * @date 2020/3/11 - 5:16 下午
 * 定义SingleLinkedList 用来管理HeroLinkedList
 */

import java.util.Stack;

public class SingleLinkedList {
/*    先初始化一个头节点，头节点不要动，动了的话，就不能通过头节点找到剩余节点了
            头节点不存放具体的数据
 */
    private HeroNode head ;


    /*
    * 将一个链表添加到当前链表，有序添加
    *
    *   直接添加会报错，只能将要添加的链表拆解为单个节点，再将节点按照number序号添加到目的链表
    * */
    public void addAnotherLinkedList(SingleLinkedList singleLinkedList){

        HeroNode temp = singleLinkedList.getHead().nextNode;
        if(temp == null){
            throw new RuntimeException("该链表只有head，没有节点，添加失败");
        }
        HeroNode nextTemp = null;
        while(true){
//            在本while中的最后，相当于已经完成了链表后移，此时的temp就是下一个节点
            if(temp == null){
                break;
            }
/*          本节点要被添加，添加的时候要把本节点的nextNode设为null
                但是要先把本节点的下一个节点先保存，否则添加完成之后，找不到本节点的下一个节点
 */
            nextTemp = temp.nextNode;
            temp.nextNode = null;
            this.addNodeByOrder(temp);
//            将之前已经保存好了的下一个节点复制给当前节点的指针，相当于完成了移位
            temp = nextTemp;
        }
    }




    /*
    * 从尾部到头打印单链表
    *       方式一、reverseNew()将链表反转再打印，但是会破坏单链表的结构，不可取
    *       方式二、可以利用栈这个数据结构，将各个节点压入到栈中，利用栈的先进后出的特点就实现了逆序打印的效果
    *
    * */
    public static void reversePrint(HeroNode heroNode){

        HeroNode temp = heroNode.nextNode;
        Stack<HeroNode> stack = new Stack<>();
        while(true){
            if(temp == null){
                break;
            }
//            push()和add()效果一样
//            stack.add(temp);
            stack.push(temp);
            temp = temp.nextNode;
        }
        while(stack.size() > 0 ){
            System.out.println(stack.pop());
        }
/*
        用迭代器遍历么，还叫个p的栈
        Iterator<HeroNode> iterator = stack.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }*/
    }

    /*
    * 单链表反转3.0
    *
    * */
    public static SingleLinkedList reverseNew(SingleLinkedList single){
//        定义一个指针，默认指向头部之后的第一个元素，这个指针指向的节点的前一个元素就是要被移动的元素
        HeroNode nextTemp = single.getHead().nextNode;
//          这个指针就是具体被移动的元素
        HeroNode currentTemp = null;
//        创建一个临时头节点，暂时用来连接反转后的链表
        HeroNode headNew = new HeroNode();
/*        不是因为临时头节点不能动，所以为临时头节点设置一个指针。
        新的临时头节点自始至终就没有动过，因为取出来的节点都是直放在新的临时头节点之后
        HeroNode headTemp = headNew;
            而是因为当最后一个currentTemp指针将所用元素取出之后，并且连接在新临时头节点之后
            currentTemp就是新临时头节点的下一个节点，刚好可以直接拿来放在原头节点的后面就完事
            而不必记录新临时头节点的地址，也就是说，执行完之后
 */
        while(true){
//            抵达原链表的末端，结束遍历
            if(nextTemp == null){
                break;
            }
            /*
            * 将遍历的链表节点依次添加到新链表头节点的尾部
            *       将节点的指针指向新节点
            * */
//            因为是单链表，所以必须先用指针标记要移动的元素，不然当原指针移动之后，考原指针找不到原指针对应节点的上一个节点
            currentTemp = nextTemp;
/*            在取原节点的时候，原指针必须先移动，不然原节点取完之后，移动原指针就没有意义了
                    这两句 currentTemp = nextTemp; nextTemp = nextTemp.nextNode; 为顺序依赖于
                        HeroNode nextTemp = single.getHead().nextNode;
                        是获取到头节点的下一个节点（我的方法就是这样）
                        还获取到的是头节点（没有意义），所以这用方法要nextTemp = nextTemp.nextNode;在前，currentTemp = nextTemp;在后
 */
            nextTemp = nextTemp.nextNode;
/*
            循环中的剩余两句，用于将获取到的节点插入到新的头节点的下一个，插进来的节点还要指向新临时头节点的原下一个节点
                1.将临时头节点指向的下一个节点指针复制给新插进来的节点的下一个节点
 */
            currentTemp.nextNode = headNew.nextNode;
//              2.将新的临时头部的下一个指针指向插进来的节点
            headNew.nextNode = currentTemp;
        }
/*      曾经有新临时头节点的指针(总共三个指针)时是这样：设置原链表的头部指向，新临时链表头的下一个节点
        但是临时头节点用完之后就没用了，而且currentTemp执行到最后，就是之向，新的临时头节点的下一个，可以直接拿来用
        总共三个指针时的设置思路：single.getHead().nextNode = headNew.nextNode;
 */
        single.getHead().nextNode = currentTemp;

        return single;
    }


    /*
    * 单链表的反转2.0
    * */
    @Deprecated
    public static SingleLinkedList reverse(SingleLinkedList single){
//        头部不可修改
        HeroNode temp = single.getHead();
//        获取链表节点的有效长度
        int validCount = getValidNodeCount(temp);
//        创建一个数组，将原链表的数据顺序存入数组，再反序读出，就能得到反序链表了
        HeroNode[] heroNode = new HeroNode[validCount];
//        1.将链表顺序写入数组
        for (int i = 0; i < validCount ; i++) {
            heroNode[i] = temp.nextNode;
            temp = temp.nextNode;
        }
        for (int i = 0; i < heroNode.length; i++) {
//            将数组中的节点的nextNode设为null
            heroNode[i].nextNode = null;
        }
        SingleLinkedList reverse = new SingleLinkedList();
        for (int i = heroNode.length - 1; i >= 0; i--) {
//            将数组反序写入新的链表
            reverse.addNodeToTheTail(heroNode[i]);
        }
        return reverse;
    }


    /*
    * 单链表的反转（腾讯面试）
    *   相比新版，调用了太多的其他静态方法（主要是根据倒数第几来获取元素）
    *       在新版中直接通过数组反转来执行
    * */
    @Deprecated
    public static SingleLinkedList reverseOld(SingleLinkedList single){

        int validCount = getValidNodeCount(single.getHead());

        HeroNode[] heroNodes = new HeroNode[validCount];

        for (int i = 1; i <= validCount; i++) {

            heroNodes[i-1] = getReverseNodeByOrder(single.getHead(),i);
        }
/*        需要在循环的外面将节点的后一位置为null，否则无法按照倒数第几取出指定节点，
                因为设置temp，已经将原来的节点更改了
             也不能用加强for循环来设置nextNode = null  ，因为加强for循环就是用这个来遍历的
        for (HeroNode heroNode : heroNodes) {

            heroNode.setNextNode(null);
        }

        用普通for循环设置nextNode = null
 */
        for (int i = 0; i < heroNodes.length; i++) {
            if(heroNodes[i] != null){

                heroNodes[i].setNextNode(null);
            }
        }


        SingleLinkedList reverse = new SingleLinkedList();
        for (int i = 0; i < heroNodes.length; i++) {

            reverse.addNodeToTheTail(heroNodes[i]);
        }
        return reverse;
    }





/*
*       获取但链表中的倒数第k个节点（新浪面试）
*       heroNode 头节点
*       reverseNumber 倒数第几个节点
* */
    public static HeroNode getReverseNodeByOrder(HeroNode heroNode, int reverseNumber){
//      先将数据遍历，获得总有效节点。总有效节点 - 倒数第几个节点 = 正数的目标节点
        int targetNumber = getValidNodeCount(heroNode) - (reverseNumber-1);
     /*   if(targetNumber < 0 ){
            throw new RuntimeException("所要的节点位置超出链表的长度");
        }*/
        HeroNode temp = heroNode;
        int forwardCount = 0;
//        再次开始遍历，到targetNumber个元素为止
        while (true){
            if(temp == null){
                throw new RuntimeException("未找到");
            }
            if(forwardCount == targetNumber){
                return temp;
            }
            forwardCount++;
            temp = temp.nextNode;
        }
    }

    /*
    * 获取该节点之后有效节点的个数，需要传递一个节点
    * */
    public static int getValidNodeCount(HeroNode head){
        HeroNode temp = head.nextNode;
        int count = 0;
        while(true){
            if(temp != null){
                count++;
            }else{
                break;
            }
            temp = temp.nextNode;
        }
        return count;
    }



    /*
    *   根据id删除节点
    * */
    public void deleteNodeById(int number){
        HeroNode temp = head;
        while (true){
            if(temp.nextNode == null){
                throw new RuntimeException("该节点number 未找到，删除失败");
            }
            if(temp.nextNode.number == number){
//                要删除的节点已找到，就在当前节点temp的后一个
//                将当前节点(temp)的指针(nextNode)指向要删除节点(temp.nextNode)的下一个节点(temp.nextNode.nextNode)
                temp.nextNode = temp.nextNode.nextNode;
/*                如果将要删除的节点的指针改为null，这里总共需要三条语句，降低执行效率
                        况且java会自动垃圾回收，没必要费周折
                    temp.nextNode.nextNode = null;
 */

                break;
            }
            temp = temp.nextNode;
        }
    }

    /*
    *   修改节点的信息，根据number来修改，number 不可以修改
    * */
    public void modify(HeroNode heroNode){
/*        事先排除头节点，方便之后的写法
            在单链表中
            关于HeroNode temp = head.nextNode; 还是
               HeroNode temp = head;            的讨论
               如果要获取当前节点的上一个节点，比如用于删除操作，或者添加操作，需要用HeroNode temp = head.nextNode;
                        因为获取本节点无法操作链表，比如删除操作，获取本节点但是无法修改上一个节点的指针区域

               如果要定位指定节点，比如修改指定节点，则用HeroNode temp = head;
 */
        HeroNode temp = head.nextNode;

        while(true){
            if(temp == null){
                throw new RuntimeException("节点 number = "+heroNode.number+"未找到，修改失败");
            }

            if(temp.number == heroNode.number){
//                根据number已经找到该节点

                temp.name = heroNode.name;
                temp.heroName = heroNode.heroName;
/*              节点数据不要乱改
                if(heroNode.nextNode != null){
                    temp.nextNode = heroNode.nextNode;
                }*/
                break;
            }
            temp = temp.nextNode;
        }

    }


    /*
    * 按照排名(number)添加节点到排名的指定位置
    *   如果已经有这个这个排名，则添加失败，给出错误提示
    * */
    public void addNodeByOrder(HeroNode heroNode){
//        因为头节点不能动，因此我们仍然通过一个辅助变量（指针）来帮助我们找到添加的位置
        HeroNode temp = head;
//        flag用于标识是否重复
        boolean valueRepetition = false;
        while(true){
//            抵达链表尾部
            if(temp.nextNode == null){
//                跳出while，放在最前能避免后面的NullPointerException
                break;
            }
//            下一个节点的序号已经比当前节点大，说明当前节点的后面就是新增节点的插入位置
            if(temp.nextNode.number > heroNode.number){
                break;
            }else if(temp.nextNode.number == heroNode.number){
//                值已经重复
                valueRepetition = true;
                break;
            }
//            不要忘了跳转下一个节点
            temp = temp.nextNode;
        }
        if(valueRepetition){
            throw new RuntimeException("当前节点"+temp.nextNode.name+"的值"+temp.nextNode.number+"与新节点"+heroNode.name+"的值"+heroNode.number+"重复，添加失败");
        }
        heroNode.nextNode = temp.nextNode;
        temp.nextNode = heroNode;
    }



    /*         不推荐使用（自己写的）
    * 按照排名(number)添加节点到排名的指定位置
    *   如果已经有这个这个排名，则添加失败，给出错误提示
    *   Deprecated该方法已过时
    * */
    @Deprecated
    public void addNodeBySequenceOld(HeroNode heroNode){
        int sequence = heroNode.number;
//        因为头节点不能动，因此我们仍然通过一个辅助变量（指针）来帮助我们找到添加的位置
        HeroNode temp = head;
//        因为是单链表，因此我们找的temp是位于添加位置之前的一个节点，否则不能插入
            while(true){
//                如果还有下一个节点
                if(temp.nextNode != null){
//                    新增节点的序号>前一个节点的序号  && 新增节点的序号<下一个节点的序号
                    if(temp.nextNode.number > sequence && temp.number < sequence){
//                        新增节点的下一个节点 = 上一个节点的下一个节点
                        heroNode.nextNode = temp.nextNode;
//                        把上一个节点的下一个节点指向新增节点
                        temp.nextNode = heroNode;
                        break;
                    }
                    if(temp.number == sequence){
                        throw new RuntimeException("节点:"+heroNode.name+"序号"+heroNode.number+"重复，添加失败");
                    }
//                    跳转下一个节点
                    temp = temp.nextNode;

                }else{
//                    没有下一个节点，已经到达最后的节点，把新节点附加在最后即可
                    temp.nextNode = heroNode;
                    break;
                }
            }
        }


    /*
    * 添加节点
    * 不考虑 编号顺序时
    * 1.找到最后一个节点
    * 2.把最后一个节点的nextNode指向新添加的节点
    * */
    public void addNodeToTheTail(HeroNode heroNode){
//        因为头节点不能动，所以我们需要一个辅助节点temp
        HeroNode temp = head;
//        遍历链表，找到最后一个节点
        while(true){
//          找到头节点，跳出循环
            if(temp.nextNode == null){
                break;
            }
/*          如果这句再if之前，且第一个节点（头节点）之后没有节点时，会报NullPointerException
            如果不是最后一个节点，就转到下一个节点
 */
            temp = temp.nextNode;
        }
//        退出while循环的时候，说明找到了最后一个节点
//        将最后一个节点的nextNode（指针）指向新的节点，将新节点附加到最后一个节点的末尾
        temp.nextNode = heroNode;
    }
    /*
    *   显示（遍历）链表
    * */
    public void showLinkedList(){
//        先判断链表是否为null
        if(head.nextNode == null){
            System.err.println("这个链表只有一个head，为null");
            return;
        }
//        使用一个辅助变量，遍历链表，
        HeroNode temp = head;
/*        while(temp.nextNode == null){
            System.out.println(temp.toString());
        }*/
        while(true){
            if(temp.nextNode == null){
                break;
            }
//            初始化的时候temp = head，这里相当于 使用head.nextNode;以不显示头部，头部没有数据
            temp = temp.nextNode;
            System.out.println(temp);
        }
    }

    public HeroNode get(int i){
        HeroNode temp = head;
        int count = 0;
        while(true){
            if(temp.nextNode == null || count == i){
                break;
            }
            count++;
            temp = temp.nextNode;
        }
        return temp;
    }

    public int size(){
        HeroNode temp = head;
        int count = 0;
        while(true){
            if(temp.nextNode == null){
                break;
            }
            count++;
            temp = temp.nextNode;
        }
        return count;
    }


    public SingleLinkedList() {
        this.head = new HeroNode();
    }

    public HeroNode getHead() {
        return head;
    }


}
